package I.堆;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;
import com.sun.org.apache.bcel.internal.generic.INEG;

import java.util.Arrays;

/**
 * 堆学习的样例
 */
public class A_BIggHeap {
    public static void main(String[] args) {
        //要求数组进行升序排序
        int[] arr = {4,6,8,5,9};
        heapsort(arr);
    }

    public static void heapsort(int arr[]){
        System.out.println("进行堆排序");

//        //分步操作
//        adjustHeap(arr,1,arr.length);
//        System.out.println("第一次调整"+ Arrays.toString(arr));//4 9 8 5 6
//
//        adjustHeap(arr,0,arr.length);
//        System.out.println("第二次调整"+ Arrays.toString(arr));//9 6 8 5 4

        //实际堆排序实现
        //1-将无序数组构建成顶堆
        for (int i= arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        //堆顶元素和末尾元素交换
        //再调整成堆 以上两步以此反复 直到序列有序
        for (int j=arr.length-1;j>0;j--){
            //交换
            int temp = 0;
            temp = arr[0];
            arr[0] = arr[j];
            arr[j] = temp;

            //调整
            adjustHeap(arr,0,j);//本次调整
        }
        System.out.println("排序之后："+Arrays.toString(arr));

    }

    /**
     * 本函数功能：将以i为根的树调整为大顶堆
     * @param arr 待调整的数组
     * @param i 非叶子节点在数组中的索引
     * @param length 表示还要对多少个元素继续调整 该数值在逐渐减少
     */
    public static void adjustHeap(int[] arr,int i,int length){

        int temp = arr[i];

        //从i开始逐渐进行调整 k= i*2+1 为i节点的左节点
        // 当第一次传入最左的时候 k遍历回来就超了 所以只会交换一次就完成左下子树的构建
        for (int k= i*2+1;k<length;k=k*2+1){
            if (k+1 < length && arr[k] < arr[k+1] ){//左节点小于右节点
                k++;

            }
            if (arr[k]>temp){
                arr[i] = arr[k];
                i=k;//i指向交换的索引k  继续比较
            }else {
                break;// 说明当前节点符合要求 可
            }
        }

        //for结束之后 表示以i为父节点的树的最大值 已经在这个子树的最顶
        arr[i] = temp;//最后一个节点交换成刚才的i节点

    }
}
